/*
 * @lc app=leetcode.cn id=148 lang=cpp
 *
 * [148] 排序链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
public:
    struct MyComp
    {
        bool operator()(ListNode *l, ListNode *r)
        {
            return l->val < r->val;
        }
    };

    ListNode *sortList(ListNode *head)
    {
        if (!head || !(head->next))
            return head;
        vector<ListNode *> v;
        auto p = head;
        while (p)
        {
            v.push_back(p);
            p = p->next;
        }
        sort(v.begin(), v.end(), MyComp());
        for(int i = 1; i < v.size(); i++)
        {
            v[i-1]->next = v[i];
        }
        (*(v.end()-1))->next = nullptr;
        return v[0];
    }
};
// @lc code=end
